package leetcode_ago.string_and_array;

/**
 * @author 美女
 * @date 2022/03/17 15:32
 * 给定一个字符串s，请你找出其中不含有重复字符的最长子串的长度。
 * eg:
 * 输入：s = "abcabcbb"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3
 **/

import java.util.HashSet;
import java.util.Set;

/**
 * 无重复字符的最长子串
 * 字符存储到set集合，如果有重复的直接之前的从set集合移除，加进来新的字符
 */
/**
 * 思路：滑动窗口
 * 以(a)bcabcbb 开始的最长字符串为 (abc)abcbb；
 * 以a(b)cabcbb 开始的最长字符串为 a(bca)bcbb；
 * 以ab(c)abcbb 开始的最长字符串为 ab(cab)cbb；
 * 以abc(a)bcbb 开始的最长字符串为 abc(abc)bb；
 * 以abca(b)cbb 开始的最长字符串为 abca(bc)bb；
 * 以abcab(c)bb 开始的最长字符串为 abcab(cb)b；
 * 以abcabc(b)b 开始的最长字符串为 abcabc(b)b；
 * 以abcabcb(b) 开始的最长字符串为 abcabcb(b).
 * 此时观察，我们需要边加入字符边移除字符。将字符逐个存入set集合，如果后面的元素有重复出现的字符，则set集合元素出集合直到无此重复元素，再将此元素入set集合
 */
public class Num3_LongestSubstring {
    public int lengthOfLongestSubstring(String s) {
        //set集合存储数组元素
        Set<Character> nums=new HashSet<>();
        int max=0;//记录最大长度
        int right=0;
        int len=s.length();
        for (int left = 0; left < len; left++) {
            if(left!=0){//left未走到空
                //移除left之前的一个元素
                nums.remove(s.charAt(left-1));
            }
            while (right<len&&!nums.contains(s.charAt(right))){
                //set集合中没有重复元素时(right对应元素是第一次添加)
                nums.add(s.charAt(right));
                right++;
            }
            //循环走到这里说明right走到了重复或者right走到了最后null
            max=Math.max(max,right-left);
        }
        return max;
    }
}

//public class Num3_LongestSubstring {
//    public static int lengthOfLongestSubstring(String s) {
//        //利用哈希集合判断元素是否重复出现
//        Set<Character> element=new HashSet<>();
//        int left=0;
//        int right=0;
//        int max=0;
//        int len=s.length();
//        for (; left < len; left++) {
//            if(left!=0){
//                element.remove(s.charAt(left-1));
//            }
//            while(right<len&&!element.contains(s.charAt(right))){
//                element.add(s.charAt(right));
//                right++;
//            }
//            //循环走到这里说明right走到了重复或者right走到了最后
//            max=Math.max(max,right-left);
//        }
//        return max;
//    }
//
//    public static void main(String[] args) {
//        String s="pwwkew";
//        int max=lengthOfLongestSubstring(s);
//        System.out.println(max);
//    }
//}
